Masala #0965

Shimoliy qutbda so'nggi yillarda dasturlashga e'tibor ancha kuchayib qoldi. Bu yili Qorbobo dasturchi elflarni bir joyga yig'ish maqsadida ular uchun ofis qurdirdi.

Dasturchi elflar oldindan alohida-alohida ishlagani uchun hech qaysi dasturchi elf bir-birini tanimaydi. Qorbobo esa jamoada hamma bir-birini tanishi muhim deb hisoblaydi. Shuning uchun u dasturchi elflarning ofisiga har kuni kelib ularni kuzata boshladi. U kuzatuvlarini yon daftariga quyidagicha yozib boradi.

• \(!\space a \space b\) - a va b elfni birga yurganini ko'rsa shu ko'rinishda belgilab qo'yadi va ularni do'stlashgan deb hisoblaydi. Bu yerda a va b natural sonlardir, chunki Qorbobo elflarini raqamlab chiqqan (Kim ham minglab elf ismlarini eslab qolardi).
• \(?\space a \space b\) - Qorbobo a va b elf do'stlashganmi deb o'ylab qolganda shu ko'rinishda belgilab qo'yadi. Bunda a elf b elf bilan va b elf c elf bilan do'st bo'lsa a elf c elf bilan ham do'st hisoblanadi (ya'ni do'stimning do'sti mening ham do'stim).

Siz Qorboboning yon daftaridagi har bir so'rovga javob bering. \(!\space a \space b\) ko'rinishidagi so'rovda a va b ni do'stlashtiring, \(?\space a \space b\) ko'rinishidagi so'rovda esa a va b elf do'st yoki do'st emasligini aniqlang.

Brinchi qatorda N va Q sonlari \((1<N\leq 2*10^5; 1\leq Q \leq 2*10^5)\), mos ravishda dasturchi elflar soni va Qorboboning yon daftaridagi so'rovlar soni. Keyingi Q ta qatorda so'rovlar:
    \(!\space a \space b\) yoki \(?\space a \space b\) ko'rinishida \((a \not= b)\), kamida bitta \(?\space a \space b\) ko'rinishida so'rov borligi kafolatlanadi.

\(!\space a \space b\) ko'rinishidagi so'rovda a va b ni do'stlashtiring, \(?\space a \space b\) ko'rinishidagi so'rovda esa a va b elf do'st bo'lsa 1 aks holda 0 chiqaring.